/**
 * @file   main.cpp
 * @author Lizhiqi 
 * @date   Fri Oct 16 15:39:13 2020
 * 
 * @brief An implement for stable quicksort  
 * 
 * 
 */

#include <iostream>
#include <cstdlib>
#include <vector>

class DATA{
private:
  int index;/**< subscript of input order*/
  double val;/**< number to be sorting*/
public:
  /** 
   * Default constructor
   * 
   */
  DATA(){};
  /** 
   * Constructor,get index and number.
   * 
   * @param _index subscript of input order
   * @param _val number to be sorting
   */
  DATA(int _index,double _val):index(_index),val(_val){}
  /** 
   * Get the index of data.
   * 
   * 
   * @return the index of data
   */
  int get_index();
  /** 
   * Get the number to be sorting.
   * 
   * 
   * @return the number to be sorting
   */
  double get_val();
  /** 
   * Print out the index and number of data.
   * 
   * 
   * @return Error code, 0 for OK.
   */
  int printout();
};
/** 
 * Partitioning the array by number.
 * 
 * @param _A data array to be dividing
 * @param _p first index to begin dividing
 * @param _q last index to end dividing
 * 
 * @return the index of the pivot
 */
int partition_val(std::vector<DATA> &_A, int _p, int _q);

/** 
 * An implement for quicksort by number.
 * 
 * @param _A data array to be sorting
 * @param _p first index to begin sorting
 * @param _q last index to end sorting
 * 
 * @return Error code, 0 for OK.
 */
int quick_sort_val(std::vector<DATA> &_A, int _p, int _q);

/** 
 * Partitioning the array by index.
 * 
 * @param _A data array to be dividing
 * @param _p first index to begin dividing
 * @param _q last index to end dividing
 * 
 * @return the index of the pivot
 */
int partition_index(std::vector<DATA> &_A, int _p, int _q);

/** 
 * An implement for quicksort by index.
 * 
 * @param _A data array to be sorting
 * @param _p first index to begin sorting
 * @param _q last index to end sorting
 * 
 * @return Error code, 0 for OK.
 */
int quick_sort_index(std::vector<DATA> &_A, int _p, int _q);

/** 
 * An implement for stable quicksort.  
 * 
 * @param _A data array to be sorting
 * 
 * @return Error code, 0 for OK.
 */
int stable_quick_sort(std::vector<DATA> &_A);

int DATA::get_index(){
  return index;
}

double DATA::get_val(){
  return val;
}

int DATA::printout(){
  std::cout << index << ":" << val;
  return 0;
}

int quick_sort_val(std::vector<DATA> &_A, int _p, int _q){
  int n=_q-_p+1;
  if (n<=1)
    return 0;
  else if (n==2){
    if (_A[_p].get_val() > _A[_q].get_val()){
      DATA tmp = _A[_p];
      _A[_p] = _A[_q];
      _A[_q] = tmp;
    }
    return 0;
  }
  else if (n==3){
       if (_A[_p+1].get_val() <= _A[_p].get_val() && _A[_p+1].get_val() <= _A[_q].get_val()){
	    if (_A[_p].get_val() <= _A[_q].get_val()){
		    DATA tmp = _A[_p+1];
		    _A[_p+1] = _A[_p];
		    _A[_p] = tmp;
		}
	    else{
		    DATA tmp = _A[_q];
		    _A[_q] = _A[_p];
		    _A[_p] = _A[_p+1];
		    _A[_p+1] = tmp;
		}
	    }
	else if (_A[_q].get_val() <= _A[_p].get_val() && _A[_q].get_val() <= _A[_p+1].get_val()){
	    if (_A[_p].get_val() <= _A[_p+1].get_val()){
		    DATA tmp = _A[_p];
		    _A[_p] = _A[_q];
		    _A[_q] = _A[_p+1];
		    _A[_p+1] = tmp;
		}
	    else{
		    DATA tmp = _A[_q];
		    _A[_q] = _A[_p];
		    _A[_p] = tmp;
		}
	    }
	}
  else{
    int k = partition_val(_A,_p,_q);
    quick_sort_val(_A,_p,_p+k-1);
    quick_sort_val(_A,_p+k+1,_q);
    return 0;
  }
}

int partition_val(std::vector<DATA> &_A, int _p, int _q){
  int n=_q-_p+1;
  if (n<=0)
    return 0;
  int left =0;
  int right = n-1;
  DATA pivot = _A[_p];
  while (left != right){
    while (_A[_p+right].get_val() >= pivot.get_val() && right > left)
      right--;
    while (_A[_p+left].get_val() <= pivot.get_val() && right > left)
      left++;
    if (right > left){
      DATA tmp = _A[_p+left];
      _A[_p+left]=_A[_p+right];
      _A[_p+right]=tmp;
      right--;
    }
  }
  _A[_p] = _A[_p+left];
  _A[_p+left] = pivot;
  return left;
}

int quick_sort_index(std::vector<DATA> &_A, int _p, int _q){
 int n=_q-_p+1;
  if (n<=1)
    return 0;
  else if (n==2){
    if (_A[_p].get_index() > _A[_q].get_index()){
      DATA tmp = _A[_p];
      _A[_p] = _A[_q];
      _A[_q] = tmp;
    }
    return 0;
  }
  else if (n==3){
       if (_A[_p+1].get_index() <= _A[_p].get_index() && _A[_p+1].get_index() <= _A[_q].get_index()){
	    if (_A[_p].get_index() <= _A[_q].get_index()){
		    DATA tmp = _A[_p+1];
		    _A[_p+1] = _A[_p];
		    _A[_p] = tmp;
		}
	    else{
		    DATA tmp = _A[_q];
		    _A[_q] = _A[_p];
		    _A[_p] = _A[_p+1];
		    _A[_p+1] = tmp;
		}
	    }
	else if (_A[_q].get_index() <= _A[_p].get_index() && _A[_q].get_index() <= _A[_p+1].get_index()){
	    if (_A[_p].get_index() <= _A[_p+1].get_index()){
		    DATA tmp = _A[_p];
		    _A[_p] = _A[_q];
		    _A[_q] = _A[_p+1];
		    _A[_p+1] = tmp;
		}
	    else{
		    DATA tmp = _A[_q];
		    _A[_q] = _A[_p];
		    _A[_p] = tmp;
		}
	    }
	}
  else{
    int k = partition_index(_A,_p,_q);
    quick_sort_index(_A,_p,_p+k-1);
    quick_sort_index(_A,_p+k+1,_q);
    return 0;
  }
}

int partition_index(std::vector<DATA> &_A, int _p, int _q){
  int n=_q-_p+1;
  if (n<=0)
    return 0;
  int left =0;
  int right = n-1;
  DATA pivot = _A[_p];
  while (left != right){
    while (_A[_p+right].get_index() >= pivot.get_index() && right > left)
      right--;
    while (_A[_p+left].get_index() <= pivot.get_index() && right > left)
      left++;
    if (right > left){
      DATA tmp = _A[_p+left];
      _A[_p+left]=_A[_p+right];
      _A[_p+right]=tmp;
      right--;
    }
  }
  _A[_p] = _A[_p+left];
  _A[_p+left] = pivot;
  return left;
}

int stable_quick_sort(std::vector<DATA> &_A){
  int n=_A.size();
  quick_sort_val(_A,0,n-1);
  int i = 1;
  int t = 0;
  while (i<n){
    if (_A[i].get_val() != _A[i-1].get_val()){
      quick_sort_index(_A,t,i-1);
      t=i;
    }
    i++;
  }
  quick_sort_index(_A,t,i-1);
  return 0;
}

int main( int argc, char *argv[]){
  int n;
  std::cin >> n;
  std::vector<DATA> A(n);
  int k = 0;
  double r;
  for (std::vector<DATA>::iterator A_iterator=A.begin();
       A_iterator != A.end();
       ++A_iterator){
    std::cin >> r;
    *A_iterator=DATA(k,r);
    k++;
  }
  std::cout << "before sorting:" << std::endl;
  std::cout << "[";
  for (std::vector<DATA>::iterator A_iterator=A.begin();
       A_iterator != A.end();
       ++A_iterator){
    (*A_iterator).printout();
    std::cout << ",";
  }
  std::cout << "\b]" << std::endl;
  stable_quick_sort(A);
  std::cout << "after sorting:" << std::endl;
  std::cout << "[";
  for (std::vector<DATA>::iterator A_iterator=A.begin();
       A_iterator != A.end();
       ++A_iterator){
    (*A_iterator).printout();
    std::cout << ",";
  }
  std::cout << "\b]" << std::endl;
  return 0;
}
